package 中等.动态规划.子序列;

import java.util.Arrays;

/**
 * 有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于
 * 实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团
 * 每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/circus-tower-lcci
 */
public class 马戏团人塔_17_08 {

    public static void main(String[] args) {

        int[] h = {8378, 8535, 8998, 3766, 648, 6184, 5506, 5648, 3907, 6773};
        int[] w = {9644, 849, 3232, 3259, 5229, 314, 5593, 9600, 6695, 4340};
        System.out.println(bestSeqAtIndex(h, w));

    }

    /**
     * 最长递增子序列
     * dp[i] 表示 i+1 长度的递增子序列，末尾元素是多少
     *
     * @param height
     * @param weight
     * @return
     */
    public static int bestSeqAtIndex(int[] height, int[] weight) {
        if (height.length == 0) return 0;  // 特判
        int[][] hw = new int[height.length][2];
        for (int i = 0; i < hw.length; i++) {
            hw[i] = new int[]{height[i], weight[i]};
        }
        // 有可能出现高度一样的人
        Arrays.sort(hw, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);

        int[] dp = new int[hw.length];
        dp[0] = hw[0][1];
        int maxPeople = 1;  // 最多人数-1 对应的是dp的索引
        for (int i = 1; i < hw.length; i++) {
            int left = 0, right = maxPeople - 1;
            int target = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (dp[mid] >= hw[i][1]) {
                    target = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            if (target == -1) {
                maxPeople++;
                target = maxPeople - 1;
            }
            dp[target] = hw[i][1];
        }
        return maxPeople;
    }

}
